package Copy;

import java.util.HashMap;
import java.util.Map;

public class Copy {
    
}
// 剑指 Offer 35. 复杂链表的复制
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
//使用hashmap的five方法
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node p = head;
        while(p!=null){
            Node newNode = new Node(p.val);
            map.put(p, newNode);
            p=p.next;
        }
        p = head;
        while(p!=null){
            Node newNode = map.get(p);
            newNode.next = map.get(p.next);
            newNode.random = map.get(p.random);
            p=p.next;
        }
        return map.get(head);
    }
}


//将新复制出来的node放在原来node的后面,
//这时原node的random的下一个就是新node的random
//最后将偶数节点拆出
/**
 * //推荐双百方法二：不需要辅助空间，但是需要额外将两个链表进行拆分，但理解难度较大
    public Node copyRandomList2(Node head) {
        if(head==null) return null;
        copy2(head);
        randomAdd2(head);
        return build2(head);
    }
    public void copy2(Node head){
         while(head!=null){
            Node copy = new Node(head.val);
            copy.next = head.next;
            head.next =copy;
            head = copy.next;
        }
    }
    public void randomAdd2(Node head){
        while(head!=null){
           if(head.random!=null) head.next.random = head.random.next;
           head=head.next.next; 
        }
    }
    public Node build2(Node head){
        //将链表拆成两个，注意要恢复原有的链表
        Node res = head.next;
        Node tmp = res;

        head.next = head.next.next;//这一步不可缺少，保证第一个复制节点对N N'的分离操作
        head = head.next;
        while(head!=null){
            tmp.next = head.next;
            head.next = head.next.next;
            tmp=tmp.next;
            head = head.next;
         }
        return res;
    }

作者：mo-fei-25
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/javashi-xian-jian-zhi-offerliang-chong-si-lu-hashm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * 
 */